package argo.hot100.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Flatten {

    public void flatten(TreeNode root) {

        Stack<TreeNode> stack = new Stack<>();
        List<TreeNode> list = new ArrayList<>();

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                list.add(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }

        for (int i = 1; i < list.size(); i++) {
            TreeNode pre = list.get(i - 1);
            TreeNode cur = list.get(i);
            pre.left = null;
            pre.right = cur;
        }

    }
}
